interface node<T> {
    //节点的key
    key: number | null;
    //节点的数据
    value: T | null;
    //节点的左节点
    leftNode: node<T> | null;
    //节点的右节点
    rightNode: node<T> | null;
}

interface BST<T> {
    //根
    root: node<T> | null;
    //插入数据
    insert(key: number, value: T): void
    //查找一个节点
    search(key: number): node<T> 
    //先序遍历
    priorityTraversal(callBack: (node: node<T>) => void, node: node<T>): void 
}

class BinarySearchTree<T> implements BST<T>{
    root: node<T> | null = null;
    constructor(key?: number, value?: T) {
        if (key && value) {
            this.root = this.createNode(key, value)
        }
    }

    insert(key: number, value: T):void {
        const newNode: node<T> = this.createNode(key, value);
        if (this.root == null) {
            this.root = newNode
        } else {
            this.insertNode(this.root, newNode)
        }
    }

    search(key: number): node<T> {
        return this.searchNode(this.root,key)
    }

    private insertNode(node:node<T>, newNode: node<T>) {
        if (node.key > newNode.key) {
            if (node.leftNode == null) {
                node.leftNode = newNode
            } else {
                this.insertNode(node.leftNode, newNode)
            }
        } else if (node.key < newNode.key) {
            if (node.rightNode == null) {
                node.rightNode = newNode
            } else {
                this.insertNode(node.rightNode, newNode)
            }
        } else {
            node.value=newNode.value
        }
    }

    priorityTraversal(callBack:Function,node=this.root):void {
        if (!node) return
        callBack(node)
        this.priorityTraversal(callBack,node.leftNode)
        this.priorityTraversal(callBack,node.rightNode)
    }

    centralTraversal(callBack: Function, node = this.root): void {
        if (!node) return
        this.centralTraversal(callBack, node.leftNode)
        callBack(node)
        this.centralTraversal(callBack, node.rightNode)
    }

    backTraversal(callBack: Function, node = this.root): void {
        if (!node) return
        this.backTraversal(callBack, node.leftNode)
        this.backTraversal(callBack, node.rightNode)
        callBack(node)
    }

    max(node = this.root): node<T> {
        if (!node.leftNode) return node
        return this.max(node.leftNode)
    }

    min(node = this.root): node<T> {
        if (!node.rightNode) return node
        return this.max(node.rightNode)
    }

    remove(key: number): boolean {
        if (this.root==null) return false
        let currentNode: node<T>|null = this.root;
        let beforeNode: node<T> | null = null;
        let direction: string;
        while (currentNode.key != key) {
            beforeNode = currentNode
            if (currentNode.key > key && currentNode.leftNode) {
                direction = 'leftNode';
                currentNode = currentNode.leftNode;
            } else {
                direction = 'rightNode';
                currentNode = currentNode.rightNode;
            }
            if (currentNode==null)return false
        }

        if (currentNode.leftNode==null&&currentNode.rightNode==null) {
            if (currentNode==this.root) {
                this.root=null
            } else {
                beforeNode[direction] = null;
            }
        } else if (currentNode.leftNode != null && currentNode.rightNode == null) {
            if (currentNode == this.root) {
                this.root = currentNode.leftNode;
                return true
            }
            beforeNode[direction] = currentNode.leftNode;
        } else if (currentNode.rightNode != null && currentNode.leftNode == null) {
            if (currentNode == this.root) {
                this.root = currentNode.leftNode;
                return true
            }
            beforeNode[direction] = currentNode.rightNode;
        } else {
            let substitute: node<T> = this.bottomNode(currentNode);
            if (currentNode == this.root) {
                this.root = substitute;
            } else {
                beforeNode[direction] = substitute;
            }
            substitute.leftNode = currentNode.leftNode;
        }
    }

    private bottomNode(node: node<T>): node<T> {
        let substitute: node<T> = node;
        let cancel: node<T> = node.rightNode;
        let beforeSubstitute: node<T> = node;
        while (cancel) {
            beforeSubstitute = substitute;
            substitute = cancel;
            cancel = cancel.leftNode;
        }
        if (substitute != node.rightNode) {
            beforeSubstitute.leftNode = substitute.rightNode;
            substitute.rightNode = node.rightNode;
        }
        return substitute
    }
    private searchNode(node: node<T>, key: number): node<T>|null {
        if (node==null) {
            return null
        } else {
            if (node.key > key) {
                return this.searchNode(node.leftNode,key)
            } else if (node.key < key) {
                return this.searchNode(node.rightNode, key)
            } else {
                return node
            }
        }
    }

    private createNode(key, value): node<T> {
        let node: node<T> = {
            key,
            value,
            leftNode: null,
            rightNode: null
        }
        return node
    }
}

const tree: BinarySearchTree<string> = new BinarySearchTree(11, 'a')
tree.insert(7, 'b')
tree.insert(15, 'c')
tree.insert(5, 'u')
tree.insert(9, 'd')
tree.insert(3, 'e')
tree.insert(8, 'f')
tree.insert(10, 'g')
tree.insert(13, 'h')
tree.insert(12, 'j')
tree.insert(20, 'k')
tree.insert(18, 'n')
console.log(tree)
tree.remove(11)
console.log(tree)